package leetcode.array;

/**
 * @Description: https://leetcode.cn/problems/max-submatrix-lcci/description/
 * @Author Ammar
 * @Create 2023/9/14 15:36
 */
public class _面试题_17_24_最大子矩阵 {

    public static void main(String[] args) {
//        new _面试题_17_24_最大子矩阵().getMaxMatrix(new int[][]{
//                new int[]{9, -8, 1, 3, -2},
//                new int[]{-3, 7, 6, -2, 4},
//                new int[]{6, -4, -4, 8, -7}
//        });
        new _面试题_17_24_最大子矩阵().getMaxMatrix(new int[][]{
                new int[]{2, 2, 2},
                new int[]{1, 1, 1},
                new int[]{6, -4, -4, 8, -7}
        });
    }

    public int[] getMaxMatrix(int[][] matrix) {
        int max = Integer.MIN_VALUE;
        int dp = 0;
        int start = 0;
        int[] ans = new int[]{-1, -1, 200, 200};
        int[] sum = null;
        for (int i = 0; i < matrix.length; i++) {
            sum = new int[matrix[0].length];
            for (int j = i; j < matrix.length; j++) {
                dp = 0;
                start = 0;
                for (int k = 0; k < sum.length; k++) {
                    sum[k] += matrix[j][k];
                    dp += sum[k];
                    if (max < dp) {
                        ans[0] = i;
                        ans[1] = start;
                        ans[2] = j;
                        ans[3] = k;
                        max = dp;
                    }
                    if (dp < 0) {
                        dp = 0;
                        start = k + 1;
                    }
                }
            }
        }
        return ans;
    }
}
